//
// Created by TNJ on 2021/6/20.
//
#include "quick_sort.h"
#include <stdio.h>
#include <stdlib.h>

static void swap(data_type_t *x, data_type_t *y){
    if(x == NULL || y == NULL){
        return;
    }

    data_type_t temp = *x;
    *x = *y;
    *y = temp;
}

static int partision(data_type_t *A, int p, int r){
    data_type_t x = A[r];  //以最后一个元素作为主元
    int i = p - 1;
    int j = p;

    while(j < r){
        if(A[j] < x){
            i++;
            swap(&A[j], &A[i]);  //比主元大的数放右边，小的数放在数组左边。
        }
        j++;
    }
    swap(&A[++i], &A[r]);  //主元作为分割点
    return i;  //返回当前分割点位置
}

void quick_sort(data_type_t *A, int p, int r){
    if(p >= r){
        return;
    }
    int q = partision(A, p, r);
    quick_sort(A, p, q - 1);
    quick_sort(A, q + 1, r);
}
